import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class LeetCode735 {
    public static void main(String[] args) {
        int[] result = asteroidCollision(new int[]{1,-1,-2,-2});
        for (int i:result) {
            System.out.print(i + " ");
        }
    }

    /**
     * 思路, 双端队列的效率远高于栈，栈耗时9ms，队列耗时2ms，
     * 1.foreach循环遍历 当前值为i
     * 2.取出栈中的顶层的一个数据last
     * 3.如果last > 0 且 i < 0,则发生碰撞，否则不发生碰撞
     * 4.如果发生碰撞，则比较last+i，如果为正数，则i不添加到栈，这时重新执行1；如果为负数，则last pop，走到步骤5；如果为0，则last pop，且i不添加到栈，这时重新执行1
     * 5.last pop之后，i要继续和stack中的值发生碰撞，直到i和last都为负或者stack为空，这时将i添加到stack。这时重新执行1
     * @param asteroids
     * @return
     */
    public static int[] asteroidCollision(int[] asteroids) {
        int[] result = {};

        Deque<Integer> stack = new ArrayDeque<>();

        int last;
        for (int i : asteroids){
            last = 0;
            if(!stack.isEmpty()){
                last = stack.peek();
            }

            if (last > 0 && i < 0){
                int sum = i + last;
                if(sum < 0){
                    while (!stack.isEmpty()){
                        stack.pop();
                        if(stack.isEmpty()){
                            stack.push(i);
                            break;
                        }

                        last = stack.peek();
                        if(last < 0 && i < 0){
                            stack.push(i);
                            break;
                        }

                        sum = i + last;
                        if(sum >= 0){
                            break;
                        }
                    }
                }

                if(sum == 0){
                    stack.pop();
                }
                continue;
            }

            stack.push(i);
        }

        result = new int[stack.size()];

        for (int i = stack.size() - 1; i >=0; i--){
            result[i] = stack.pop();
        }

        return result;
    }
}
